Users are increasingly performing tasks using remote computing resources, which may be offered through a shared-resource environment. This has many advantages, as users do not have to purchase and maintain dedicated hardware and software, and instead can pay for only those resources that are utilized at any given time, where those resources typically will be managed by a resource provider. Users can perform tasks such as storing data or executing applications using various types of resources offered by the resource provider. In many cases a user might want to utilize a secure connection, such as a secure shell (SSH) connection, for purposes such as secure login over a network over which the user may otherwise have little control. For multi-tenant environments, however, the use of SSH connections can require specific SSH keys to be defined with per-user authentication and authorization. This approach can be cumbersome to manage and does not take advantage of the multi-tenant nature of the environment.